class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 栈排序
     * @param a int整型vector 描述入栈顺序
     * @return int整型vector
     */
    vector<int> solve(vector<int>& a) {
        // write code here
        bool vis[50010]={0};//是否在栈中
        int target=a.size();//不在栈中最大的那个数
        stack<int> st;
        vector<int> ret;
        for(auto e:a)
        {
            if(e!=target)
            {
                st.push(e);
                vis[e]=1;
            }
            else {

                ret.push_back(e);
                target--;
                while(vis[target]==1)
                {
                    target--;
                }

                while(!st.empty() &&target<st.top())//当栈外最大的数小于栈内数时，用栈内数
                {
                    ret.push_back(st.top());
                    st.pop();


                }
                
            }

        }
        return ret;
    }

};